package com.yin.algorithms;

import com.yin.Sort;

public class CountSort implements Sort {

    @Override
    public void sort(int[] arr) {

        //结果数组
        int[] result = new int[arr.length];

        //数组中的最大值
        int max = findMax(arr);

        //数组中的最小值
        int min = findMin(arr);

        //计数桶
        int[] bucket = new int[max - min + 1];

        //偏移映射，本质为使最小值在桶内的下标为0
        int offset = -min;

        //计数
        for (int cur : arr) {

            //cur    -> 当前元素    -5              2
            //offset -> 偏移       5               0
            //bucket -> 计数桶     [-5 + 5]++      [2 + 0]++
            bucket[cur + offset]++;
        }

        //累加
        for(int j = 1; j < bucket.length; j++) {

            //bucket[num] -> 最后一个num出现的下标
            bucket[j] = bucket[j] + bucket[j - 1];
        }

        //放回结果数组
        for(int k = arr.length - 1; k >= 0; k--) {
            //反向遍历原数组，在计数桶里寻找这个元素对应的最后出现的下标，并按照这个位置放回结果数组
            //arr[k] -> 原数组倒数第一个数
            //arr[k] + offset -> 原数组倒数第一个数对应的最后出现的位置是第几，非下标
            //bucket[arr[k] + offset] - 1 -> 原数组倒数第一个数对应的最后出现的位置 -> arr[k]元素在结果数组中的正确位置
            //减1是因为计数桶从1开始算，结果数组从0开始算
            /*
            *          0  1  2
            *   bucket[2, 1, 2]
            *
            *   result[0, 0, 1, 2, 2]
            *
            *   result数组中第(bucket[0])个元素值为0，下标为(bucket[0] - 1)
            * */
            result[--bucket[arr[k] + offset]] = arr[k];
        }

        //同步回原数组
        for(int y = 0; y < arr.length; y++) {

            arr[y] = result[y];
        }
    }

    private int findMax(int[] arr) {

        int max = arr[0];
        for(int i = 1; i < arr.length; i++) {

            max = Math.max(arr[i], max);
        }

        return max;
    }

    private int findMin(int[] arr) {

        int min = arr[0];
        for(int i = 1; i < arr.length; i++) {

            min = Math.min(arr[i], min);
        }

        return min;
    }
}
